class Solution
{
public:
    int minimumTimeToInitialState(string word, int k)
    {
        int n = word.size();
        vector<int> next(n, -1);
        int j = -1;
        for (int i = 1; i < n; ++i)
        {
            while (j != -1 && word[i] != word[j + 1])
            {
                j = next[j];
            }
            if (word[i] == word[j + 1])
            {
                j++;
            }
            next[i] = j;
        }

        j = next.back();
        while (true)
        {
            if (j == -1)
            {
                return ceil((double)n / k);
            }
            int len = n - j - 1;
            if (len % k == 0)
            {
                return len / k;
            }
            j = next[j];
        }
        return -1;
    }
};